import java.util.HashSet;
import java.util.Set;

//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
//   示例 1:
//        输入: s = "abcabcbb"
//        输出: 3
//        解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//        示例 2:
//        输入: s = "bbbbb"
//        输出: 1
//        解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//        示例 3:
//        输入: s = "pwwkew"
//        输出: 3
//        解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//             请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//        示例 4:
//        输入: s = ""
//        输出: 0
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class Solution3 {
    //1.暴力破解 效率较低
//    public static int lengthOfLongestSubstring(String s) {
//        if (s.equals("")||s.length()==0){
//            return 0;
//        }else {
//            int result = 0;
//            for (int j=0;j<s.length();j++){
//                HashSet<String> set=  new HashSet();
//                int one = 0;
//                for (int i =j ;i<s.length();i++){
//                    if (set.contains(s.substring(i,i+1))){
//                         break;
//                    }else {
//                        one++;
//                        set.add(s.substring(i,i+1));
//                    }
//                if (one>result) {
//                    result = one;
//                }
//                }
//            }
//            return result;
//        }
//    }

    //从大到小排除  超时！！！
//    public static int lengthOfLongestSubstring(String s) {
//
//        for (int i=s.length();i>0;i--){
//            for (int j=0;i+j<=s.length();j++){
//                String tem = s.substring(j,i+j);
//                HashSet hashSet = new HashSet();
//                for (int k=0;k<i;k++){
//                    hashSet.add(tem.substring(k,k+1));
//                }
//                if (i==hashSet.size()){
//                    return i;
//                }
//            }
//        }
//        return 0;
//    }

        public static int lengthOfLongestSubstring1(String s) {
            // 记录字符上一次出现的位置
            int[] last = new int[128];
            for(int i = 0; i < 128; i++) {
                last[i] = -1;
            }
            int n = s.length();

            int res = 0;
            int start = 0; // 窗口开始位置
            for(int i = 0; i < n; i++) {//窗口结束位置
                int index = s.charAt(i);
                start = Math.max(start, last[index] + 1);//当前窗口结束位置的相同值如果有在窗口内，则开始位置到相同值的下一位开始
                res   = Math.max(res, i - start + 1);//每次计算新窗口大小(右指针一定子啊动，左指针可能在动)，如果比当前最大值还大则赋值
                last[index] = i;
            }

            return res;
        }
        public static int lengthOfLongestSubstring(String s) {
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;//rk结束位置(右指针)  ans结果
            for (int i = 0; i < n; ++i) {//i 左指针
                if (i != 0) {
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk+1  < n && !occ.contains(s.charAt(rk+1 ))) {
                    // 不断地移动右指针
                    occ.add(s.charAt(rk+1 ));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i +1);
            }
            return ans;
        }
        public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abbeawea"));
        System.out.println(myTest("abbeawea"));
//            String s = "abcd";
//            int index = s.charAt(0);
//            System.out.println(index);
    }

    public static int myTest(String s) {
            Set<Character> set = new HashSet<Character>();
            int right = -1;
            int max = 0;
            for (int i=0;i<s.length();i++){
                if (i!=0){
                    set.remove(s.charAt(i-1));//左指针移动 set中去掉不包含的那个字符（移动前最左边）
                }
                while (right+1<s.length()&&!set.contains(s.charAt(right+1))){
                    right++;
                    set.add(s.charAt(right));
                }
                max = Math.max(max,right - i +1 );
            }
            return max;
    }
}
